package 动态规划.dp声明正序And倒序.射箭比赛这道题的思维发散;

import org.junit.Test;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/25 22:38
 */
public class 美团318dp倒推 {
    /*
     这个题 ,要更加的 搞清楚!
     为之后的路 打下基础!

     这个题，真的服气！
     */

    // 2023/8/16 , 直接使用记忆化搜索, 然后遍历 dp 但是 过 两个 用例!
    public static void main2(String[] args) {
//        solve();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();

        int prices[][] = new int[n][2];
        for (int i = 0; i < n; i++) {
            prices[i][0] = sc.nextInt();
            prices[i][1] = sc.nextInt();
        }
        Integer dp[][][] = new Integer[n + 1][m + 1][k + 1];

        int recursion = recursion(0, m, k, prices, dp);

        int ans = Integer.MAX_VALUE;

        /*
         其实 只需要 遍历 j 也就是 money 就行了, 因为 最优解 必是 从 0 开始 ,优惠券 为 k 时 取得,
         因为 范围 越大, 优惠券越多 花的钱也是越少的,  这具有单调性的

         但是 不知道为什么 过不了?
         */
        for (int j = 0; j <=m ; j++) {
            if(dp[0][j][k] != null && dp[0][j][k] == recursion){
                ans = Math.min(ans,j);
            }
        }
        System.out.println(recursion + " " + ans);
    }


    public static int recursion(int index, int rest, int k, int prices[][], Integer[][][] dp) {
        if (dp[index][rest][k] != null) {
            return dp[index][rest][k];
        }
        if (rest == 0 || index == prices.length) { // 这里 没有 判断 rest 是否越界 ,是因为 我会在下面的决策中, 进行 一个判读 , 如果 rest 不符合, 根本就不会进到这里来
            return dp[index][rest][k] = 0;
        }
        int ans1, ans2 = 0;
        // no buy
        ans1 = recursion(index + 1, rest, k, prices, dp);

        // buy
        // full buy , discount buy
        if (rest >= prices[index][0]) { // 决策的 前置条件
            ans2 = recursion(index + 1, rest - prices[index][0], k, prices, dp) + 1;
        }
        if (k > 0 && rest >= prices[index][1]) {
            ans2 = Math.max(ans2, recursion(index + 1, rest - prices[index][1], k - 1,prices,dp) + 1);
        }
        return dp[index][rest][k] = Math.max(ans1, ans2);
    }





    /*
     真他妈离谱：
     dp 表缓存的 是所有情况的 可能 ， 意思是 所有的 情况都已经被记录下来了！ （ 所以求 在 买 商品 数量最多的情况下，花费最少的 这一种情况！ 只需要
       遍历 dp 表，  找到 数量 = max ， 并且 rest 最小的）


       这个版本就是  学长的 那个 写法！， 不过 学长的那种 还 使用滚动数组进行  **空间优化**；
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int money = sc.nextInt();
        int y = sc.nextInt();
        int nums[][] = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = sc.nextInt();
            nums[i][1] = sc.nextInt();
        }
        int dp[][][] = new int[n + 1][money + 1][y + 1];

        for (int index = n - 1; index >= 0; index--) {
            /*
             woc， 把 ticket  变为 从 0  就   ac 了！
             如果 ticket 不从 0 开始的 话， 会有一些 用例过不了！
             */
            for (int ticket = 0; ticket <= y; ticket++) {
                dp[index][0][ticket] = 0;
                for (int rest = 0; rest <= money; rest++) {
                    int ans0 = 0, ans1 = 0, ans2 = 0;
                    // no choose
                    ans0 = dp[index + 1][rest][ticket];
                    // 原价买 , 这里跟回溯不太一样的, 需要进行一个余额的判断, 否则会数组越界异常
                    if (rest - nums[index][0] >= 0)
                        ans2 = dp[index + 1][rest - nums[index][0]][ticket] + 1;
                    // 半价 买, 判断 rest 和 ticket 是否够买
                    if (ticket >= 1 && rest - nums[index][1] >= 0)
                        ans1 = dp[index + 1][rest - nums[index][1]][ticket - 1] + 1;

                    dp[index][rest][ticket] = Math.max(ans1, Math.max(ans2, ans0));
                }
            }
        }


//         可以对下 面的 遍历 进行一个优化！
//         ====

        int max = dp[0][money][y],rest = money;
        for(int i = 0;i < n;i++){
            for(int j = 1;j <= money;j++){
                for(int k = 1;k <= y;k++){
                    if (dp[i][j][k] == max){
                        rest = Math.min(rest,j);
                    }
                }
            }
        }

        System.out.println(dp[0][money][y] + " " + rest);
        /*

            可以 A ，但是 这种优化 没什么 鸟用
         */
        int mx = dp[0][money][y];
        for (int j = 0; j <= money; j++) {
            for (int i = 0; i <= n; i++) {
                for (int k = 0; k <= y; k++) {
                    if (dp[i][j][k] == mx) {
                        System.out.println(mx + " " + j);
                        return;
                    }
                }
            }
        }

    }


    // ======================================= 能过大部分的


    public static void mainI(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int money = sc.nextInt();
        int y = sc.nextInt();
        int nums[][] = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = sc.nextInt();
            nums[i][1] = sc.nextInt();
        }
        int dp[][][] = new int[n + 1][money + 1][y + 1], path[][][] = new int[n + 1][money + 1][y + 1]; // 0 表示 没买路径 . 2 表示 原价买, 1 表示半价买

        for (int index = n - 1; index >= 0; index--) {
//            dp[index][0][]
            for (int ticket = 1; ticket <= y; ticket++) {
                dp[index][0][ticket] = 0;
                for (int rest = 1; rest <= money; rest++) {
                    int ans0 = 0, ans1 = 0, ans2 = 0;
                    // no choose
                    ans0 = dp[index + 1][rest][ticket];
                    // 原价买 , 这里跟回溯不太一样的, 需要进行一个余额的判断, 否则会数组越界异常
                    if (rest - nums[index][0] >= 0)
                        ans2 = dp[index + 1][rest - nums[index][0]][ticket] + 1;
                    // 半价 买, 判断 rest 和 ticket 是否够买
                    if (ticket >= 1 && rest - nums[index][1] >= 0)
                        ans1 = dp[index + 1][rest - nums[index][1]][ticket - 1] + 1;

                    int[][] sort = {{ans0, 0}, {ans1, 1}, {ans2, 2}};
                    Arrays.sort(sort, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
                    path[index][rest][ticket] = sort[2][1];
//                    dp[index][rest][ticket] = Math.max(ans0,Math.max(ans1,ans2));
                    dp[index][rest][ticket] = sort[2][0];
                }
            }
        }
        int max = dp[0][money][y], rest = money;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= money; j++) {
                for (int k = 1; k <= y; k++) {
                    if (dp[i][j][k] == max) {
                        rest = Math.min(rest, j);
                    }
                }
            }
        }


//        System.out.println(dp[0][money][y]);
//        // 可不可以 只用一个 for循环,就能解决, 把 ticket 直接 也别 for 循环了!
//        int rest = money,ticket = y;
//        for(int i = 0;i < n;i++){
//            if(path[i][rest][ticket] == 1){
//                rest -= nums[i][1];
//                ticket--;
//            }else if(path[i][rest][ticket] == 2){
//                rest -= nums[i][0];
//            }
//        }


//        for (int i = 0; i < n; i++) {
//            for(int ticket = y;ticket >= 1 ;ticket--){
////                if (rest <= 0){
////                    System.out.println(money);
////                    System.out.println(dp[0][money][y] + " " + (money - rest));
////                    return;
////                }
//                if(path[i][rest][y] == 1){ //原价
//                    rest -= nums[i][0];
//                }else if(path[i][rest][ticket] == 2){
//                    rest -= nums[i][1];
//                }
//            }
//        }
        System.out.println(dp[0][money][y] + " " + rest);
    }


    @Test
    public void test() {
        int[][] sort = {{4, 0}, {4, 1}, {4, 2}};
        Arrays.sort(sort, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        for (int nums[] : sort) {
            System.out.println(Arrays.toString(nums));
        }
    }

/*
 想的 还怪 花哨 ，说实话！
 */
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int money = sc.nextInt();
        int y = sc.nextInt();
        int nums[][] = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = sc.nextInt();
            nums[i][1] = sc.nextInt();
        }
        Integer[][][] dp = new Integer[n + 1][money + 1][y + 1];
        int path[][][] = new int[n + 1][money + 1][y + 1];
//        Integer dp[][][] = new Integer[n + 1][money + 1][y + 1];
        int ans = recursion(0, money, y, dp, nums, path);


        int rest = money, ticket = y;
        for (int i = 0; i < n; i++) {
            if (path[i][rest][ticket] == 1) {
                rest -= nums[i][1];
                ticket--;
            } else if (path[i][rest][ticket] == 2) {
                rest -= nums[i][0];
            }
        }
        System.out.println(ans + " " + (money - rest));
    }


    public static int recursion(int index, int rest, int count, Integer dp[][][], int nums[][], int[][][] path) {
        if (rest == 0 || index == nums.length) {
            return 0;
        }
        if (dp[index][rest][count] != null) {
            return dp[index][rest][count];
        }
        int ans0 = 0, ans1 = 0, ans2 = 0;
        // no choose
        ans0 = recursion(index + 1, rest, count, dp, nums, path);
        // 原价 前提是 能买
        if (rest - nums[index][0] >= 0) {
            ans2 = recursion(index + 1, rest - nums[index][0], count, dp, nums, path) + 1;
        }
        // 半价
        if (rest - nums[index][1] >= 0 && count >= 1) {
            ans1 = recursion(index + 1, rest - nums[index][1], count - 1, dp, nums, path) + 1;
        }
        int[][] sort = {{ans0, 0}, {ans1, 1}, {ans2, 2}};
        Arrays.sort(sort, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        path[index][rest][count] = sort[2][1];
        return dp[index][rest][count] = Math.max(ans1, Math.max(ans2, ans0));
    }

}
